"""
目标：

交换两个链点在链表中的位置
不改变其他链点在链表中的位置

举例：

1->2->3->4->5

input:1 4 output:4->2->3->1->5

思路：

采用 insert 的思想，对于要交换的两个链点 d1 d2，各自声明新的 D1 D2 ，使 D1=d1, D2=d2
然后把 然后再根据 d1 d2 的位置，改变索引的位置，即完成交换的全部操作
"""


# 定义单链表节点
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


# 定义单链表
class LinkedList:
    def __init__(self):
        self.head = None

    def print_list(self):  # 遍历链表，并将元素依次打印出来
        print("linked_list:")
        temp = self.head
        new_list = []
        while temp is not None:
            new_list.append(temp.data)
            temp = temp.next
        print(new_list)

    def insert(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

    # 交换结点
    def swap_nodes(self, d1, d2):
        prevD1 = None
        prevD2 = None
        # 相同元素, 不需要交换
        if d1 == d2:
            return
        else:
            # 遍历找到值等于d1的元素
            D1 = self.head
            while D1 is not None and D1.data != d1:
                prevD1 = D1
                D1 = D1.next
            # 遍历找到值等于d2的元素
            D2 = self.head
            while D2 is not None and D2.data != d2:
                prevD2 = D2
                D2 = D2.next
            # 如果D1和D2都不存在, 不需要交换
            if D1 is None and D2 is None:
                return
            # D1存在, 将D1的上一个结点的next指向D2
            if prevD1 is not None:
                prevD1.next = D2
            # D1的上一个结点不存在, D1是头结点, 把头结点指向D2就好了
            else:
                self.head = D2
            # D2存在, 将D2的上一个结点的next指向D1
            if prevD2 is not None:
                prevD2.next = D1
            # D2的上一个结点不存在, D2是头结点, 把头结点指向D1就好了
            else:
                self.head = D1
            # 把D1的next指向原来D2的next, 把D2的next指向原来D1的next
            temp = D1.next
            D1.next = D2.next
            D2.next = temp


if __name__ == '__main__':
    list = LinkedList()
    list.insert(5)
    list.insert(4)
    list.insert(3)
    list.insert(2)
    list.insert(1)
    list.print_list()
    list.swap_nodes(1, 4)
    print("After swapping")
    list.print_list()

